package com.lbc.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
         // 测试
        // 先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");

        // 创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 加入
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        // 加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
//        singleLinkedList.addByOrder(hero3);
        // 遍历
        singleLinkedList.list();

        // 测试一下反转功能
        reverseList(singleLinkedList.getHead());
        System.out.println("反转后的单链表~~");
        singleLinkedList.list();
        System.out.println("再反转回去接着测试后面的~~");
        reverseList(singleLinkedList.getHead());

        System.out.println("逆序打印单链表,没有改变原链表的结构~~");
        reversePrint(singleLinkedList.getHead());

        // 测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();

        // 删除一个节点
        singleLinkedList.delete(1);
        singleLinkedList.delete(4);
//        singleLinkedList.delete(2);
//        singleLinkedList.delete(3);
        System.out.println("删除后的链表情况~~");
        singleLinkedList.list();

        // 测试一下 求单链表中的有效节点的个数
        System.out.println("有效节点的个数=" + getLength(singleLinkedList.getHead())); //2

        // 得到倒数第k个元素
        HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
        System.out.println("res=" + res);
    }


    /**
     * 要求：获取到单链表的有效节点的个数（如果是带头结点的链表，需要不统计头节点）
     * @param head  链表的头节点
     * @return  返回的就是有效节点的个数
     */
    public static int getLength (HeroNode head) {
        if (head.next == null) { // 空链表
            return 0;
        }
        int length = 0;
        // 定义一个辅助变量,这里我们没有统计头节点
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 查找单链表中的倒数第k个节点
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        }
        // 1.先从左到右遍历，得到链表总的长度 getLength()
        int size = getLength(head);
        // 2.得到size后，从第一个节点开始遍历（size-index)个节点即得
        if (index <= 0 || index > size) {
            // 先做一个index的校验
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
        // 上述方法由于要先得到长度，所以还存在优化的空间
        /**
           优化方案一：
              从前往后遍历，每到一个节点停一下，检测从该节点到最后一个节点的距离是否为index（好像时间复杂度还大一点）

           优化方案二：
               定义两指针，先让第一个指针走k步，然后两指针一起走，直到先走的那个指针走到末尾（好像next操作次数一样呀）

           说用递归的都是傻子，不想重复
        */
    }

    //  反转单链表
    public static void reverseList (HeroNode head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        //  定义一个辅助指针(变量)，遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;  // 指向当前节点的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        // 遍历原来的链表，每遍历一个节点，就将去取出，并放在新的链表reverseHead的最前端
        while (cur != null) {
            next = cur.next; // 保存当前节点的下一个节点，后面还需要
            cur.next = reverseHead.next; // 将cur的下一个节点指向新的篮板链表的最前端
            reverseHead.next = cur;  // 头插法结束
            cur = next;  // 让cur后移
        }
        // 将head.next 指向 reverseHead.next -- 实现了单链表的反转
        head.next = reverseHead.next;
    }

    // 从尾到头打印单链表
    // 方式一：先反转，再遍历  --> 这样做破坏了原单链表的结构，不可取
    // 方式二：可以利用栈的先进后出的效果，实现逆序打印单链表的效果  --> 如果单链表的数据量过大不也栈溢出了吗？？？
    public static void reversePrint (HeroNode head) {
        if (head.next == null) {
            // 空链表，不能打印
            return;
        }
        // 创建一个栈，将各个节点压入栈
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        while (cur != null) {
            stack.add(cur);
            cur = cur.next;
        }
        // 将栈中的节点进行打印，pop 出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    // 课后练习：合并两个有序单链表，合并后依然有序

}

// 定义SingleLinkedList，管理我们的英雄
class SingleLinkedList {
    // 先初始化一个头节点，头节点不要动
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    // 添加节点到单向链表
    // 不考虑编号顺序时：
    //  1.找到当前链表的最后节点
    //  2.将最后节点的next指向新的节点
    public void add (HeroNode heroNode) {
        // 因为head不能动，所以需要一个辅助节点
        HeroNode temp = head;
        // 遍历链表，找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        // 退出循环时，temp指向了链表的最后
        temp.next = heroNode;
    }

    // 按英雄排名添加（有该英雄则添加失败）
    public void addByOrder (HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false; // 标识添加的英雄是否存在
        while (true) {
            if (temp.next == null) {
                // 说明temp已经在链表的最后
                break;
            }
            if (temp.next.no > heroNode.no) {
                // 位置找到，就在temp后面添加
                break;
            }
            if (temp.next.no == heroNode.no) {
                // 说明希望添加的英雄已经存在了
                flag = true;
                break;
            }
            temp = temp.next;  // 后移
        }
        // 判断flag的值
        if (flag) {
            System.out.printf("准备插入的英雄编号%d 已经存在了\n", heroNode.no);
        } else {
            // 插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //  修改节点的信息，根据no编号
    public void update(HeroNode newHeroNode) {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 找到需要修改的节点
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;  // 已经遍历完这个链表了
            }
            if (temp.no == newHeroNode.no) {
                // 找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nikeName = newHeroNode.nikeName;
        } else {
            System.out.printf("没有找到编号%d 的节点，不能修改", newHeroNode.no);
        }
    }

    // 删除一个节点
    public void delete(int no) {
        // 先找到待删节点的前一个节点
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;  // temp后移，遍历
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的节点%d 不存在\n", no);
        }
        // 被删除的节点，将不会有其他引用指向，回被垃圾回收机制回收
    }

    // 显示链表[遍历]
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            System.out.println(temp.next);
            temp = temp.next;
        }
    }


}

//  定义HeroNode , 每个HeroNode 对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nikeName;
    public HeroNode next;  // 指向下一个节点

    // 构造器
    protected HeroNode (int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nikeName = nickName;
    }

    //  为了显示方便，重新toString()
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nikeName + "]";
    }

}